package com.heima.leetcode.practice;

/**
 * leetcode 37. 解数独
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/15 15:02
 */
public class E37 {
    /*

     [["5","3",".",".","7",".",".",".","."]
     ,["6",".",".","1","9","5",".",".","."]
     ,[".","9","8",".",".",".",".","6","."]
     ,["8",".",".",".","6",".",".",".","3"]
     ,["4",".",".","8",".","3",".",".","1"]
     ,["7",".",".",".","2",".",".",".","6"]
     ,[".","6",".",".",".",".","2","8","."]
     ,[".",".",".","4","1","9",".",".","5"]
     ,[".",".",".",".","8",".",".","7","9"]]

     思路就是逐行逐个元素遍历，如果遇到数字则跳过，如果遇到空格，则for循环选一个填进去，
     继续处理下一个元素，如果当前选入的元素不满足要求，可以剪枝

     */

    /**
     * 数独表空格填入数字，解数独
     *
     * @param board 数独表
     */
    public void solveSudoku(char[][] board) {
        boolean[][] rowUsed = new boolean[9][9]; // 统计一行的每个数值是否被使用过
        boolean[][] colUsed = new boolean[9][9]; // 统计一列的每个数值是否被使用过
        boolean[][] boxUsed = new boolean[9][9]; // 统计九宫格的每个数值是否被使用过
        // 根据数独开始条件，初始化三个数组
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];
                if (num == '.') continue; // 跳过空格
                rowUsed[i][num - '1'] = true;
                colUsed[j][num - '1'] = true;
                boxUsed[i / 3 * 3 + j / 3][num - '1'] = true;
            }
        }
        dfs(0, 0, board, rowUsed, colUsed, boxUsed);
    }

    /**
     * 递归实现，思路就是逐行逐个元素遍历，如果遇到数字则跳过，如果遇到空格，
     * 就进入当前递归的主要逻辑，一次递归就是处理一个空格，递归顺序：从左往右从上到下
     * 主要逻辑：尝试填入1-9，如果填入的数字不合法，就剪枝，如果填入的数字合法，就继续递归处理下一个空格
     * 值得注意的是，可能会因为不适当的选取数字顺序，导致后续的某个递归处理某个后面的空格时发现1-9都不满足
     * 这种时候，说明前面的填入的数字其实是不合法的，所以回溯到上一层，重新选择数字，
     * 还有一点需要注意，并不是说每次递归的时候都需要回溯，有且仅有在当前递归后面的一次递归处理空格无解的情况下回溯
     *
     * @param startRow 开始行索引
     * @param startCol 开始列索引，两者一起决定某个元素的位置
     * @param board    数独表
     * @param rowUsed  当前行已使用的数字
     * @param colUsed  当前列已使用的数字
     * @param boxUsed  当前元素所处九宫格已使用的数字
     * @return 当前递归是否成功找到解
     */
    private boolean dfs(int startRow,
                        int startCol,
                        char[][] board,
                        boolean[][] rowUsed,
                        boolean[][] colUsed,
                        boolean[][] boxUsed) {
        // 找到第一个空格
        while (startRow < 9 && board[startRow][startCol] != '.') {
            startCol++;
            if (startCol == 9) {
                startRow++;
                startCol = 0;
            }
        }
        // startRow == 9，说明所有数字都被填好了，返回true
        if (startRow == 9) {
            return true; // 所有数字都被填好了
        }
        // 当前空格尝试填入1-9
        for (int num = 1; num <= 9; num++) {
            // 判断当前数字是否合法
            if (rowUsed[startRow][num - 1]
                    || colUsed[startCol][num - 1]
                    || boxUsed[startRow / 3 * 3 + startCol / 3][num - 1]) continue;
            // 填入当前数字
            board[startRow][startCol] = (char) (num + '0');
            // 标记当前数字已使用
            rowUsed[startRow][num - 1] = true;
            colUsed[startCol][num - 1] = true;
            boxUsed[startRow / 3 * 3 + startCol / 3][num - 1] = true;
            // 指向下一个元素
            if (++startCol == 9) {
                startRow++;
                startCol = 0;
            }
            // 递归处理下一个元素，并返回下一个空格的处理结果
            boolean nextExists = dfs(startRow,
                    startCol,
                    board,
                    rowUsed,
                    colUsed,
                    boxUsed);
            // 如果下一个空格处理成功，返回true
            if (nextExists) return true;
            // 如果下一个空格处理失败，说明当前数字不合法，回溯，继续尝试下一个数字
            if (--startCol == -1) {
                startRow--;
                startCol = 8;
            }
            rowUsed[startRow][num - 1] = false;
            colUsed[startCol][num - 1] = false;
            boxUsed[startRow / 3 * 3 + startCol / 3][num - 1] = false;
            board[startRow][startCol] = '.';
        }
        return false;
    }
}
